//给你两个整数 m 和 n 表示一个下标从 0 开始的 m x n 网格图。同时给你两个二维整数数组 guards 和 walls ，其中 guards[i]
// = [rowi, coli] 且 walls[j] = [rowj, colj] ，分别表示第 i 个警卫和第 j 座墙所在的位置。 
//
// 一个警卫能看到 4 个坐标轴方向（即东、南、西、北）的 所有 格子，除非他们被一座墙或者另外一个警卫 挡住 了视线。如果一个格子能被 至少 一个警卫看到，
//那么我们说这个格子被 保卫 了。 
//
// 请你返回空格子中，有多少个格子是 没被保卫 的。 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
//输出：7
//解释：上图中，被保卫和没有被保卫的格子分别用红色和绿色表示。
//总共有 7 个没有被保卫的格子，所以我们返回 7 。
// 
//
// 示例 2： 
//
// 
//
// 输入：m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
//输出：4
//解释：上图中，没有被保卫的格子用绿色表示。
//总共有 4 个没有被保卫的格子，所以我们返回 4 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= m, n <= 10⁵ 
// 2 <= m * n <= 10⁵ 
// 1 <= guards.length, walls.length <= 5 * 10⁴ 
// 2 <= guards.length + walls.length <= m * n 
// guards[i].length == walls[j].length == 2 
// 0 <= rowi, rowj < m 
// 0 <= coli, colj < n 
// guards 和 walls 中所有位置 互不相同 。 
// 
//
// Related Topics 数组 矩阵 模拟 👍 17 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

// 自己写
class Solution2257
{
    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {

        int[][] mark = new int[m][n];
        for (int[] g : guards) {
            mark[g[0]][g[1]] = 1;
        }
        for (int[] w : walls) {
            mark[w[0]][w[1]] = 2;
        }

        int redCnt = 0;
        int gwCnt = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mark[i][j] == 1) {
                    gwCnt++;
                    redCnt += func(m, n, mark, i, j);
                }
                if (mark[i][j] == 2) {
                    gwCnt++;
                }
            }
        }

        // 总格子数 - 感染数 - (警卫数+墙数), 剩下的就是没有保卫的数
        return m * n - redCnt - gwCnt;
    }

    // 染红色 9
    // 返回感染的格子数, 也即保卫的格子数
    int func(int m, int n, int[][] mark, int row, int col) {
        // if (mark[i][j] == 9) {
        //     return;
        // }

        int cnt = 0;
        if (mark[row][col] == 1) {
            for (int r = row - 1; r >= 0; r--) {
                int v = mark[r][col];
                if (v == 1 || v == 2) break;
                if (v == 9) continue;
                mark[r][col] = 9;
                cnt++;
            }

            for (int r = row + 1; r < m; r++) {
                int v = mark[r][col];
                if (v == 1 || v == 2) break;
                if (v == 9) continue;
                mark[r][col] = 9;
                cnt++;
            }

            for (int c = col - 1; c >= 0; c--) {
                int v = mark[row][c];
                if (v == 1 || v == 2) break;
                if (v == 9) continue;
                mark[row][c] = 9;
                cnt++;
            }

            for (int c = col + 1; c < n; c++) {
                int v = mark[row][c];
                if (v == 1 || v == 2) break;
                if (v == 9) continue;
                mark[row][c] = 9;
                cnt++;
            }
        }

        return cnt;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
